package edu.cmu.cs211.compression.util;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.AbstractQueue;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.SortedSet;

/**
 * An unbounded priority {@linkplain Queue queue}. This queue orders elements
 * according to an order specified at construction time, which is specified
 * either according to their <i>natural order</i> (see {@link Comparable}), or
 * according to a {@link java.util.Comparator}, depending on which constructor
 * is used. A priority queue does not permit <tt>null</tt> elements. A
 * priority queue relying on natural ordering also does not permit insertion of
 * non-comparable objects (doing so may result in <tt>ClassCastException</tt>).
 * <p>
 * The <em>head</em> of this queue is the <em>least</em> element with
 * respect to the specified ordering. If multiple elements are tied for least
 * value, the head is one of those elements -- ties are broken arbitrarily. The
 * queue retrieval operations <tt>poll</tt>, <tt>remove</tt>,
 * <tt>peek</tt>, and <tt>element</tt> access the element at the head of
 * the queue.
 * <p>
 * A priority queue is unbounded, but has an internal <i>capacity</i> governing
 * the size of an array used to store the elements on the queue. It is always at
 * least as large as the queue size. As elements are added to a priority queue,
 * its capacity grows automatically. The details of the growth policy are not
 * specified.
 * <p>
 * This class and its iterator implement all of the <em>optional</em> methods
 * of the {@link Collection} and {@link Iterator} interfaces. The Iterator
 * provided in method {@link #iterator()} is <em>not</em> guaranteed to
 * traverse the elements of the PriorityQueue in any particular order. If you
 * need ordered traversal, consider using <tt>Arrays.sort(pq.toArray())</tt>.
 * <p>
 * <strong>Note that this implementation is not synchronized.</strong> Multiple
 * threads should not access a <tt>PriorityQueue</tt> instance concurrently if
 * any of the threads modifies the list structurally. Instead, use the
 * thread-safe {@link java.util.concurrent.PriorityBlockingQueue} class.
 * <p>
 * Implementation note: this implementation provides O(log(n)) time for the
 * insertion methods (<tt>offer</tt>, <tt>poll</tt>, <tt>remove()</tt>
 * and <tt>add</tt>) methods; linear time for the <tt>remove(Object)</tt>
 * and <tt>contains(Object)</tt> methods; and constant time for the retrieval
 * methods (<tt>peek</tt>, <tt>element</tt>, and <tt>size</tt>).
 */
public class MyPriorityQueue<T> extends AbstractQueue<T> {
	// fields
	private static final int DEFAULT_INITIAL_CAPACITY = 11;
	private Object[] heap;
	private int size;
	private Comparator<? super T> comparator;
	private boolean naturalOrdering;	// true if comparator ordering isn't specified by the user
	
	// returns the default, natural ordering comparator
	private static <T> Comparator<? super T> getDefaultComparator()
    {
        return new Comparator<T>()
        {
            public int compare(T a, T b)
            {
            	return ((Comparable<T>)a).compareTo(b);
            }
        };
    }
	
	/**
	 * Creates a <tt>PriorityQueue</tt> with the default initial capacity (11)
	 * that orders its elements according to their natural ordering (using
	 * <tt>Comparable</tt>).
	 */
	public MyPriorityQueue() {
		size = 0;
		heap = new Object[DEFAULT_INITIAL_CAPACITY];
		comparator = getDefaultComparator();
		naturalOrdering = true;
	}

	/**
	 * Creates a <tt>PriorityQueue</tt> with the specified initial capacity
	 * that orders its elements according to their natural ordering (using
	 * <tt>Comparable</tt>).
	 * 
	 * @param initialCapacity
	 *            the initial capacity for this priority queue.
	 * @throws IllegalArgumentException
	 *             if <tt>initialCapacity</tt> is less than 1
	 */
	public MyPriorityQueue(int initialCapacity) {
		if (initialCapacity < 1)
			throw new IllegalArgumentException();
		
		size = 0;
		heap = new Object[DEFAULT_INITIAL_CAPACITY];
		comparator = getDefaultComparator();
		naturalOrdering = true;
	}

	/**
	 * Creates a <tt>PriorityQueue</tt> with the specified initial capacity
	 * that orders its elements according to the specified comparator.
	 * 
	 * @param initialCapacity
	 *            the initial capacity for this priority queue.
	 * @param comparator
	 *            the comparator used to order this priority queue. If
	 *            <tt>null</tt> then the order depends on the elements'
	 *            natural ordering.
	 * @throws IllegalArgumentException
	 *             if <tt>initialCapacity</tt> is less than 1
	 */
	public MyPriorityQueue(int initialCapacity, Comparator<? super T> comparator) {
		if(comparator!=null)
			this.comparator = comparator;
		if(initialCapacity < 0)
			throw new IllegalArgumentException();
		size = 0;
		heap = new Object[initialCapacity];
		naturalOrdering = false;
	}
	
	/**
	 * Creates a <tt>PriorityQueue</tt> that orders its elements according to the specified comparator.
	 * 
	 * @param comparator
	 *            the comparator used to order this priority queue. If
	 *            <tt>null</tt> then the order depends on the elements'
	 *            natural ordering.
	 */
	public MyPriorityQueue(Comparator<? super T> comparator) {
		if(comparator!=null)
			this.comparator = comparator;
		size = 0;
		heap = new Object[DEFAULT_INITIAL_CAPACITY];
		naturalOrdering = false;
	}

	/**
	 * Creates a <tt>PriorityQueue</tt> containing the elements in the
	 * specified collection. The priority queue has an initial capacity of 110%
	 * of the size of the specified collection or 1 if the collection is empty.
	 * If the specified collection is an instance of a
	 * {@link java.util.SortedSet} or is another <tt>PriorityQueue</tt>, the
	 * priority queue will be sorted according to the same comparator, or
	 * according to its elements' natural order if the collection is sorted
	 * according to its elements' natural order. Otherwise, the priority queue
	 * is ordered according to its elements' natural order.
	 * 
	 * @param c
	 *            the collection whose elements are to be placed into this
	 *            priority queue.
	 * @throws ClassCastException
	 *             if elements of the specified collection cannot be compared to
	 *             one another according to the priority queue's ordering.
	 * @throws NullPointerException
	 *             if <tt>c</tt> or any element within it is <tt>null</tt>
	 */
	public MyPriorityQueue(Collection<? extends T> c) {
		size = 0;
		heap = new Object[(int) (c.size() * 1.1)];
	
		if(c.size()== 0)
			throw new IllegalArgumentException();
		
		if(c instanceof SortedSet)
		{
			this.comparator = ((SortedSet)c).comparator();
			naturalOrdering = false;
		}
		else if(c instanceof PriorityQueue)
		{
			this.comparator = ((PriorityQueue)c).comparator();
			naturalOrdering = false;
		}
		else if(c instanceof MyPriorityQueue)
		{
			this.comparator = ((MyPriorityQueue)c).comparator();
			naturalOrdering = false;
		}
		else
		{
			comparator = getDefaultComparator();
			naturalOrdering = true;
		}
		// iterate through the collection, insert each element into the queue
		Iterator<? extends T> itr = c.iterator();
		while(itr.hasNext())
		{ 
			Object o;
			if( (o = itr.next()) == null)
				throw new NullPointerException();
			if(!Comparable.class.isInstance(o) && this.naturalOrdering != false)
				throw new ClassCastException();
			offer((T)o);
		}
	}

	/**
	 * Returns the comparator used to order this collection, or <tt>null</tt>
	 * if this collection is sorted according to its elements natural ordering
	 * (using <tt>Comparable</tt>).
	 * 
	 * @return the comparator used to order this collection, or <tt>null</tt>
	 *         if this collection is sorted according to its elements natural
	 *         ordering.
	 */
	public Comparator<? super T> comparator () {
		if(this.naturalOrdering)
			return null;
		return this.comparator;
	}

	/**
   * Returns the number of elements in this collection.  If this collection
   * contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
   * <tt>Integer.MAX_VALUE</tt>.
   *
   * @return the number of elements in this collection
   */
	@Override
    public int size () 
	{
		return this.size;
	}

	/**
	 * Inserts the specified element into this priority queue.
	 * 
	 * @return <tt>true</tt>
	 * @throws ClassCastException
	 *             if the specified element cannot be compared with elements
	 *             currently in the priority queue according to the priority
	 *             queue's ordering.
	 * @throws NullPointerException
	 *             if the specified element is <tt>null</tt>.
	 */
	public boolean offer (T o) {
		if(o == null)
			throw new NullPointerException();

		if(!Comparable.class.isInstance((T)o) && this.naturalOrdering != false)
			throw new ClassCastException();
		// double the size of the queue if full
		if(isFull())
			resize();
		
		// make a whole at the end of the queue, increment the size
		int hole = ++size;
		// percolation up until find the correct position of o
		for( ; hole>1 && this.comparator.compare(o, (T) heap[hole/2]) < 0; hole/=2)
			heap[hole] = heap[hole/2];
		//insert o
		heap[hole] = o;
		return true;
	}
	
	/* returns true if the queue is full, false otherwise*/
	public boolean isFull() {
		if (size +1 == this.heap.length)
			return true;
		else
			return false;
	}
	
	/* returns true if queue is empty, false otherwise */
	public boolean isEmpty() {
		return size==0;
	}
	
	/* returns the min element of the queue, null if queue is empty */
	public T findMin() {
		if(isEmpty())
			return null;
		return (T) heap[1];
	}
	
	/* double the size of the queue */
	public void resize() {
		Object[] newHeap = new Object[heap.length * 2];
		for(int i = 0; i < heap.length; i++)
			newHeap[i] = heap[i];
		heap = newHeap;
	}
	/**
   * Retrieves and removes the head of this queue,
   * or returns <tt>null</tt> if this queue is empty.
   *
   * @return the head of this queue, or <tt>null</tt> if this queue is empty
   */
	public T poll () {
		if(isEmpty())
			return null;
		// grab min element
		Object min = heap[1];
		// temporarily place the last element at top
		heap[1] = heap[size--];
		percolateDown(1);
		return (T) min;
	}

	private void percolateDown(int hole)
	{
		int child = hole;
		Object tmp = heap[hole];
		for( ; hole*2 <=size; hole=child)
		{
			child = hole*2;
			// select the smaller child
			if(child!=size && comparator.compare((T)heap[child+1],(T)heap[child])<0)
				child++;
			// bubble up if child is smaller than tmp
			if(comparator.compare((T)heap[child], (T) tmp) < 0)
				heap[hole] = heap[child];
			// exit the loop if not bubbling
			else break;
		}
		// place tmp
		heap[hole] = tmp;
	}
	/**
   * Retrieves, but does not remove, the head of this queue,
   * or returns <tt>null</tt> if this queue is empty.
   *
   * @return the head of this queue, or <tt>null</tt> if this queue is empty
   */
	public T peek () {
		if(isEmpty())
			return null;
		return (T)heap[1];
	}

	/**
	 * Returns an iterator over the elements in this queue. The iterator does
	 * not return the elements in any particular order. The iterator does not
	 * support the remove operation.
	 * 
	 * @return an iterator over the elements in this queue.
	 */
	@Override
    public Iterator<T> iterator ()
    {
			return new Iterator<T>()
			{
				int i = 1;
				@Override
				public boolean hasNext() {
					return (i) <= size;
				}
	
				@Override
				public T next() {
					if(hasNext())
						return (T)heap[i++];
						throw new NoSuchElementException();
				}

				@Override
				public void remove() {
					// TODO Auto-generated method stub
					
				}
			};
		}	
}
